/*
 * File:   leafnode.h
 * Author: Stripped
 *
 * Created on April 18, 2009, 10:02 AM
 */

#ifndef _LEAFNODE_H
#define _LEAFNODE_H

#include "Node.h"
#include "KeyValueEntity.h"
#include <stdexcept>
#include "TreeUtils.h"
#include <algorithm>
#include <stdio.h>
#include <string>

using namespace std;

template <class TKey, class TValue>
class KeyValuePair;

template <class TKey, class TValue>
class Node;

template <class TKey, class TValue>
class LeafNode : public Node <TKey, TValue>
{
    //typedef KeyValuePair<TKey, TValue> KeyValuePair;
    typedef Node<TKey, TValue> INode;

public:
    /**
     * Constructor: Creates a LeafNode
     *
     * @param  nodeMaxSize: is the max size of the node, default value = 2
     * @param  parent: node that will be parent of the new node, default value = NULL
     */
    LeafNode(unsigned int nodeMaxSize = 2, INode* parent = NULL) : Node<TKey, TValue>(nodeMaxSize, parent){}

    /**
     * Destructor
     *
     */
    virtual ~LeafNode() {}

    /**
     * Adds a key-value pair into the tree.
     *
     * Throws an std::logic_exception if the key exists in the tree.
     *
     * @param  TKey key which identifies the key-value pair
     * @param  TValue value of the key-value pair
     */
    virtual INode* put(const TKey& key, const TValue& value)
    {
        typename std::vector< KeyValuePair<TKey, TValue> >::iterator it;

        // search for the right place were to insert the new value
        it = std::lower_bound(this->elements.begin(), this->elements.end(), KeyValuePair<TKey, TValue>(key));

        // if the key exists, throw exception
        if (it != this->elements.end() && it->key == key)
        {
            throw ios_base::failure("Clave duplicada.");
        }

        // inserts the element
        it = this->elements.insert(it, KeyValuePair<TKey, TValue>(key, value));

        // checks if the node is in an invalid state (only overflow possible)
        if (this->isOverflow())
        {
            // fix the overflow (split and promote)
            return this->fixOverflow();
        }

        return NULL;
    }

    /**
     * Returns the value of a specified key
     *
     * Throws std::logic_error if the key does not exists
     *
     * @param  TKey key which value you wish to retrieve
     * @return TValue value which matches the given key
     */
    virtual TValue& get(const TKey& key)
    {
        typename std::vector< KeyValuePair<TKey, TValue> >::iterator it;

        // generic binary search
        it = TreeUtils::binary_search(this->elements.begin(), this->elements.end(), KeyValuePair<TKey, TValue> (key));

        // if the element does not exists, throw exception
        if (it == this->elements.end())
        {
            throw ios_base::failure("Key not found");
        }

        return it->value;
    }

    /**
     * Removes an element from the node.
     * NOTE: Since remove is only intended as part of an update, it does not fixes underflow after deletion.
     *
     * Throws std::logic_error if the key is not present
     *
     * @param key to remove
     */
    virtual void remove (const TKey& key)
    {
        typename std::vector< KeyValuePair<TKey, TValue> >::iterator it;

        // generic binary search
        it = TreeUtils::binary_search(this->elements.begin(), this->elements.end(),  KeyValuePair<TKey, TValue> (key));

        // if the element does not exists, throw exception
        if (it == this->elements.end())
        {
            throw ios_base::failure("Key not found, deletion is not posible.");
        }

        this->elements.erase(it);

        // checks if the node is in an invalid state (only underflow is possible)
        if (!this->isUnderflow())
        {
            // fix the underflow (redistribute or concat) would probably need to change the return element of this function
            // return this->fixUnderflow();
            // TODO: redistribute or concat
             // Redistribución: Se busca si en alguno de los siblings(“siblings” se llama a los nodos vecinos, que
             // dependen del mismo padre) tiene mas claves que el mínimo. En caso afirmativo se realiza una
             // rotación de claves que involucra al nodo, al sibling y al padre, bajando la clave del padre, que se
             // encuentra de separador entre el sibling y el nodo, al nodo con underflow y subiendo del sibling un
             // elemento para cubrir el lugar del separador.
             // Concatenación: En el caso que la redistribución no puede llevarse a cabo, se procede a unir el
             // nodo afectado con alguno de sus siblings y con el separador en el nodo padre, quedando un único
             // nodo entre los afectados (operación inversa al alta con split).

        }
    }

    /**
     * Searchs for a specified key and returns true if exists
     *
     * @param  TKey key which value you wish to find
     * @return bool True if the key exists, False if it doesn't
     */
    virtual bool has(const TKey& key) const
    {
       return std::binary_search(this->elements.begin(), this->elements.end(),  KeyValuePair<TKey, TValue> (key));
    }

    /**
     * counts the amount of elements in the node.
     *
     * @return returns the elements count
     */
    virtual unsigned int elementsCount() const
    {
        return this->elements.size();
    }

    /**
     * Swaps the element for the smaller in the node.
     *
     * @param element: KeyValuePair to swap
     * @return returns the old KeyValuePair that was replaced
     */
    virtual  KeyValuePair<TKey, TValue>  swap( KeyValuePair<TKey, TValue>  element)
    {
         KeyValuePair<TKey, TValue>  auxElement(this->elements.front());
        this->elements[0] = element;

        return auxElement;
    }

    /**
     * Removes the first element of the list
     *
     */
    virtual void forceRemoveFirstElement()
    {
        this->elements.erase(this->elements.begin());
    }


    /**
     * For debuggin purposes, it prints the tree
     *
     */
 /*
    virtual void printNode()
    {
        unsigned int pos = 0;

        cout << "< " << endl;

        while (pos < this->elements.size())
        {
            //std::cout << "<" << this->elements[pos].key << "," << this->elements[pos].value << ">" << " ";
            cout << this->elements[pos].key << " ";
            pos++;
        }
        cout << ">";
    }
*/
    /**
     * Fills the vector sent as parameter with all the elements of the tree (recursive)
     *
     * @param vector to fill
     */
    virtual void getAllElements(std::vector< KeyValuePair<TKey, TValue> > &vector)
    {
        for (unsigned int i = 0; i < this->elements.size(); i++)
        {
            vector.push_back( this->elements[i]);
        }
    }

protected:
    /**
     * Splits the node in half.
     *
     * Creates a new sibling node with all the elements bigger (to the right) of the key on the "split position" (order /2).
     *
     * @return returns the new  Node<TKey, TValue> sibling
     */
    INode* split()
    {
        // if I'm a leaf node, all new siblings will be leaf nodes.
        INode* sibling = new LeafNode<TKey, TValue>(this->nodeMaxSize, this->parentNode);
        unsigned int splitPosition = this->nodeMaxSize / 2;

        // move all the elements to the new created sibling
        for (unsigned int i = splitPosition+1; i < (unsigned int)(this->nodeMaxSize + 1) ; i++)
        {
            // sibling->forceAddElement(this->elements.at(i));
            sibling->forcePushBackElement(this->elements.at(i));
        }

        // remove all the elements moved to the new sibling from the original node
        this->elements.erase(this->elements.begin() + splitPosition, this->elements.end());

        return sibling;
    }

private:
    LeafNode(const LeafNode<TKey, TValue>&);
    LeafNode<TKey, TValue>& operator=(const LeafNode<TKey, TValue>&);
};

#endif  /* _LEAFNODE_H */
